1. Field of Invention
The invention relates to a system and method for controlling colors rendered by a printer or displayed on a monitor using more than three colors, excluding black, to reduce the visibility of error diffusion dot patterns with similar image quality as vector error diffusion, but with much less computation than using semi-vector quantization.
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owners have no objection to the facsimile reproduction, by anyone, of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
2. Description of Related Art
Scalar error diffusion is a well known technique for reducing continuous tone images to a pattern of black and white spots for rendering using a binary device. A process for error diffusion is disclosed in an article entitled xe2x80x9cAn Adaptive Algorithm for Spatial Grayscalexe2x80x9d by Robert W. Floyd and Louis Steinberg, Proceedings of the Society of Information Display, Vol. 17, pp. 75-77 (1976), hereby incorporated by reference in its entirety. That process uses an algorithm that analyzes whether to render a dot at a certain location within an image based on a comparison of the continuous tone data with a threshold value. Grayscale levels within the continuous tone image above a chosen threshold are assigned a dot to be rendered and those below the threshold are not assigned a dot to be rendered. If the threshold corresponds to midway between black and white, the method always chooses the closer of black and white. The inherent error resulting from such a choice is propagated in specified amounts to adjacent picture elements or pixels not yet analyzed to change the pixels prior to thresholding. This method produces a representation of a grayscale tone over a small area encompassing several dots that is more accurate than conventional halftoning. Hence, the error in the intensity of the digital image is diffused and, on average, zero.
The fraction of the error added to each neighboring pixel depends on a set of weights, the total error being multiplied by the weight corresponding to a given neighboring pixel and then added to the value of that neighbor pixel. The choice of weight can greatly affect the image quality, and much has been said about weights appropriate for giving pleasing results. Examples of weights other than those in the original Floyd and Steinberg algorithm may be found in papers by Jarvis, Judice, and Ninke, xe2x80x9cA Survey of Techniques for Display of Continuous-Tone Pictures on Bilevel Displaysxe2x80x9d, Computer Graphics and Image Processing, Vol. 5, pp. 13-40, (1976), Stucki, xe2x80x9cImage Processing for Document Reproductionxe2x80x9d, Advances in Digital Image Processing, pp. 177-218, New York, Plenum, (1979), and Fan, xe2x80x9cA Simple Modification of Error Diffusion Weightsxe2x80x9d, Proceedings of the ISandT 46th Annual Conference, pp. 113-114, Boston (1993) and in U.S. Pat. No. 5,353,127 to Shiau et al., hereby incorporated by reference in their entireties.
In the case of color, however, one cannot just apply simple scalar error diffusion to each color component independently. To do so would produce noisy images. For example, a light blue can be produced by magenta and cyan pixels. But if the magenta and cyan are processed independently, then some pixels may have both magenta and cyan, yielding blue, while others have no color at all, giving white. This mixture of white, blue, magenta and cyan will have more contrast and look noisier than pixels of magenta and cyan alone. The process of independently processing each channel can result in any and all of the eight possible pixel colors distributed over an image area.
However, the problem of image noisiness can be reduced by a method of vector error diffusion. In vector error diffusion processing methods, the color chosen for each pixel is the color in a selected color space closest to the desired value, where the desired value is the input value adjusted by the errors diffused from neighboring pixels. This modification tends to confine the pixel colors to a subset near the input value and reduces noise. What is known as vector error diffusion was described in a paper by Venable et al., xe2x80x9cSelection and Use of Small Color Sets for Pictorial Displayxe2x80x9d, Proceedings of the ISandT Annual Meeting, Rochester (1990) and in a paper by Miller et al. xe2x80x9cColor Halftoning Using Error Diffusion and a Human Visual System Modelxe2x80x9d, Proceedings of the ISandT Annual Meeting, Rochester, (1990), hereby incorporated by reference in their entireties.
In vector error diffusion, colors are treated as points in a three-dimensional space, with the colors printable or displayable at given pixel discrete locations within that space. When a continuous tone color is to be displayed, the closest displayable or printable colorant is selected. The error, i.e., the difference between the input color and added error, and the output colorant, is calculated as a vector in color space. Here, the xe2x80x9cclosenessxe2x80x9d might be the simple distance in color space or a weighted distance based on the human visual model. The vector is the difference between the desired, ideal, color and the available colorant. The error associated with that vector is then diffused in the same way as in scalar error diffusion.
There are, however, some problems with vector error diffusion. One such problem is the difficult three-dimensional computation required to find the closest colorant at each pixel. Second, the method is unstable for ideal colors that are near the boundary of the available color gamut provided by,an image rendering device. With these ideal color values, the addition of error adjustment from neighboring pixels can take a requested ideal color value out of the available color gamut. As a result, the nearest colorant to the requested color generates an error that leads even further outside the gamut. As a result, the vector error diffusion process collapses or produces unstable results. A third problem with some implementations of vector error diffusion is that processing may still not select the optimal set of colorants. For example, the vector error diffusion method may produce a gray from white and black pixels, where a smoother image might be produced if cyan, magenta and yellow were used because there would be less luminance contrast.
U.S. patent application Ser. No. 6,072,591, entitled xe2x80x9cSum and Difference Error Diffusionxe2x80x9d filed by Steven J. Harrington on Jun. 30, 1997, assigned to the same assignee as the present invention and hereby incorporated by reference in its entirety, teaches a significantly different process for color error diffusion. Rather than applying vector or scalar error diffusion directly to the colors, this process minimizes errors by using the sum and differences of the colors. Using this method, error diffusion is only carried out on three channels with a simple decision tree selecting the output color at each pixel. However, that method for color error diffusion is not applicable when more than three colors other than black are used during color image rendering. Therefore, the process disclosed in U.S. patent application Ser. No. ""691 is not applicable when there is more than one way to render a given requested color using various combinations of many colors. This is because the process was designed for use with a cmyk image rendering system.
Additionally, U.S. Pat. No. 6,014,233, entitled xe2x80x9cError Diffusion for Color Images with Semi-Vector Quantizationxe2x80x9d, filed by Zhigang Fan and Steven J. Harrington on Jun. 9, 1998, assigned to the same assignee as the present invention and incorporated by reference in its entirety, teaches a method for color error diffusion that uses both sum and difference and scalar error diffusion. Sum and difference error diffusion is performed on the two darkest colors of the three colors used in a system to render color images. Scalar error diffusion is performed on the remaining, lightest color. By performing vector error diffusion for only the darker, more visually perceived colors, the image is rendered while minimizing perceived noise. However, because scalar error diffusion is performed for only the lighter, less visually perceived color, the increased amount of error associated with the scalar error diffusion is less perceptible. For example, semi-vector error diffusion would use sum and difference error diffusion for rendering magenta and cyan and scalar vector error diffusion for rendering yellow. Accordingly, relatively good image quality is provided while reducing the amount of computation performed during image rendering.
The exemplary embodiments of the invention provide an image rendering system and method using a sum-and-difference error diffusion technique that may be utilized in conjunction with image rendering using more than three colorants. The colorants may be arbitrary and/or redundant. The sum-and-difference error diffusion technique involves two sets of steps. First, the amount of colorant to be placed at a particular location is determined. Second, the specific colorants are selected that comprise the amount of colorant to be rendered. When determining the specific colorants to be used, the total number of colorant requests for a particular location are summed, including any associated error adjustments resulting from rendering colorant at locations other than the particular location. Subsequently, the colorant requests are sorted and selected to fulfill the color image rendering.
In a first exemplary embodiment, the adjusted colorant requests, i.e., colorant requests adjusted by errors resulting from colorant rendering at other locations, are sorted so that the largest requests are selected as part of the requested amount of colorant at the particular location.
In a second exemplary embodiment, additional rules beyond sorting the adjusted colorant requests based on size are utilized during sorting of the adjusted colorant requests. For example, the allowed colorant combinations are limited during the sort of the adjusted colorant requests. This is preferred when efficiency is desired; however, limiting the colorant combinations during the sort does not provide flexibility during image processing.
Alternatively, in a third exemplary embodiment, sorting the adjusted colorant requests is performed and completed and the results of that sort are used to index a look up table. This exemplary embodiment is preferable when there are more complicated rules implemented to provide greater system flexibility.
In a fourth exemplary embodiment, a weighting factor system is used to adjust the colorant requests and is integrated into the sorting process.